//===------- SeqAccessesInfo.h -- Sequential accesses analysis --*- C++ -*-===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// Utilize LLVM single entry single exit Region pass to analyze sequential
// accesses in a Function.
//
//===----------------------------------------------------------------------===//
#ifndef REFLOW_MEMORY_SEQUENTIALACCESSESINFO
#define REFLOW_MEMORY_SEQUENTIALACCESSESINFO

#include "reflow/Diagnostics/Diagnostic.h"
#include "reflow/Memory/ReflowAA.h"
#include "reflow/SCEV/ScalarEvolutionCanon.h"
#include "reflow/Support/LoopPredicateAnalysis.h"

#include "llvm/Analysis/PostDominators.h"
#include "llvm/Analysis/RegionInfo.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Instruction.h"
#include "llvm/Pass.h"
#include "llvm/Support/Debug.h"
#include "llvm/Transforms/Utils/OrderedInstructions.h"
#include <cassert>
#include <deque>

namespace llvm {

class SeqAccessesRegionNode;

/// Represents an analysis zone
using Zone =
    std::pair<std::pair<BasicBlock *, BasicBlock *>, SeqAccessesRegionNode *>;

/// Helper type for analysis candidate accesses' chain
using ChainID = const Value *;
using InstList = SmallVector<Instruction *, 8>;
using InstListMap = MapVector<ChainID, InstList>;

void initializeSeqAccessesInfoPassPass(PassRegistry &);
Pass *createSeqAccessesInfoPass();

/// @brief Collects info for diagnosting why we fail to analyze/extend a
/// SeqAccess.
class DiagFailureInfo {
  // maxinum kind of enum FailureType
  static constexpr size_t MAX_DIAG_KINDS = 8;

public:
  enum FailureType {
    AccessClobbered = 0,
    AccessInCondBranch = 1,
    CouldNotAnalyzePattern = 2,
    IncompatibleStride = 3,
    SideEffect = 4,
    NonSimpleMemoryAccess = 5,
    InsufficientAlignment = 6,
    UnsupportedAccessType = 7,
    ExposeInDataflowRegion = MAX_DIAG_KINDS
  };

 private:
  /// Represents the access intruction that fail for inferring a SeqAccess
  const Instruction *AI;

  /// Represents the failure type
  const FailureType FT;

  /// Records if the failing is on an inferred SeqAccess
  bool ExtendAnalyzedSA;

  /// Records the side effect instruction that blocks the inference of a
  /// SeqAccess
  Instruction *SI;

  /// Records the context loop of this diagnostic
  Loop *L;

public:
  /// Gets the number of kinds the diagnostics have
  size_t getNumDiagKinds() const { return MAX_DIAG_KINDS + 1; }

  DiagFailureInfo(const Instruction *AI, FailureType FT,
                  bool ExtendAnalyzedSA = false, Instruction *SI = nullptr,
                  Loop *L = nullptr)
      : AI(AI), FT(FT), ExtendAnalyzedSA(ExtendAnalyzedSA), SI(SI), L(L) {}

  /// Gets the access intruction that fail for inferring a SeqAccess
  const Instruction *getFailureInst();

  /// Gets the type of failure
  FailureType getFailureType();

  /// Return true if we fail to extend an inferred SeqAccess. Else return false
  bool isExtendAnalyzedSA();

  /// Gets the side effect instruction that blocks the inference
  Instruction *getSideEffectInst();

  /// Gets the context loop of this diagnostic
  Loop *getDiagLoop();
};

/// @brief Represents a chain of sequntial accesses
class SeqAccess {
public:
  enum AccessDirection { LOAD = 0, STORE = 1 };

private:
  LLVMContext *Ctx;
  const DataLayout *DL;

  /// Represents the underlying object of this SeqAccess
  Value *UObj;

  /// Represents the access direction of this SeqAccess
  const AccessDirection Dir;

  /// Represents the start address of this SeqAccess
  const SCEV *Start;

  /// Represents the length of this SeqAccess
  const SCEV *Len;

  /// Represents the access data type of this SeqAccess
  Type *AccessTy;

  /// Represents the begin position of this SeqAccess
  Instruction *BP;

  /// Represents the end position of this SeqAccess
  Instruction *EP;

  /// Collects all accesses in the SeqAccess in the sequential order
  SetVector<Instruction *> Accesses;

  /// Collects predicate terms of this SeqAccess
  SetVector<std::pair<Value *, ConstantInt *>> Preds;

public:
  SeqAccess(LLVMContext *Ctx, const DataLayout *DL, Value *UObj,
            AccessDirection Dir, const SCEV *Start, const SCEV *Len,
            Type *AccessTy, Instruction *BP, Instruction *EP,
            ArrayRef<Instruction *> Accesses,
            ArrayRef<std::pair<Value *, ConstantInt *>> Preds = None)
      : Ctx(Ctx), DL(DL), UObj(UObj), Dir(Dir), Start(Start), Len(Len),
        AccessTy(AccessTy), BP(BP), EP(EP),
        Accesses(Accesses.begin(), Accesses.end()),
        Preds(Preds.begin(), Preds.end()) {}

  SeqAccess(const SeqAccess &) = delete;
  SeqAccess &operator=(const SeqAccess &) = delete;

  /// Check if \p I is the begin instruction of the SeqAccess
  bool isSeqAccessChainBegin(Instruction *I) const;

  /// Check if \p I is in this SeqAccess
  bool contains(Instruction *I) const;

  /// Gets the underlying object of this SeqAccess
  Value *getUnderlyingObj() const;

  /// Gets the access direction of this SeqAccess
  SeqAccess::AccessDirection getDirection() const;

  /// Gets the start address of this SeqAccess
  const SCEV *getStart() const;

  /// Gets the length of this SeqAccess
  const SCEV *getLen() const;

  /// Gets all the accesses of this SeqAccess
  SetVector<Instruction *> getAccesses() const;

  /// Gets the number of accesses in this SeqAcces
  size_t getSeqAccessChainSize() const;

  /// Gets all the predicate terms of this SeqAccess
  SetVector<std::pair<Value *, ConstantInt *>> getPreds() const;

  /// Check whether this SeqAccess is under any predicate terms
  bool isPredicated() const;

  /// Gets the first access of the SeqAccess
  Instruction *getFirstAccess() const;

  /// Gets the begin instruction of the SeqAccess
  Instruction *getSeqAccessChainBegin() const;

  /// Gets the access data type of this SeqAccess
  Type *getAccessTy() const;

  /// Gets the equivalent store size access data type of this SeqAccess
  Type *getAccessStoreTy() const;

  /// Gets the begin position of this SeqAccess
  Instruction *getBeginPosition() const;

  /// Gets the end position of this SeqAccess
  Instruction *getEndPosition() const;

  void print(raw_ostream &OS) const;
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  void dump() const;
#endif
};

class SeqAccessesZoneNode;

/// @brief A node to record analysis region
class SeqAccessesRegionNode {
  friend class SeqAccessesInfo;
  friend class BBsAnalyzer;
  friend class RegionAnalyzer;
  friend class LoopAnalyzer;

protected:
  using SeqAccessesZoneNodeListMap =
      MapVector<Zone, std::unique_ptr<SeqAccessesZoneNode>>;

private:
  LLVMContext *Ctx;
  const DataLayout *DL;

  /// Represents the corresponding region of this SeqAccessesRegionNode
  Region *R;

  /// Collects all instructions in the region that may store
  InstList MayStoreRefs;

  /// Collects all instructions in the region that may load
  InstList MayLoadRefs;

  /// Collects all instructions in the region that may wrap
  InstList MayWraps;

  /// Collects all SeqAccessesZoneNodes under this SeqAccessesRegionNode
  SeqAccessesZoneNodeListMap SeqAccessesZoneNodes;

  /// Add a new processed SeqAccessesZoneNode
  void addSeqAccessesNode(SeqAccessesZoneNode *SN);

  /// Clean up SeqAccessesZoneNodes
  void clear();

public:
  SeqAccessesRegionNode(LLVMContext *Ctx, const DataLayout *DL, Region *R) :
      Ctx(Ctx), DL(DL), R(R) {}

  SeqAccessesRegionNode(const SeqAccessesRegionNode &) = delete;
  SeqAccessesRegionNode &operator=(const SeqAccessesRegionNode &) = delete;

  ~SeqAccessesRegionNode() { clear(); }

  LLVMContext *getContext() const { return Ctx; }
  const DataLayout *getDataLayout() const { return DL; }

  /// Gets the region corresponding to this SeqAccessesRegionNode
  Region *getRegion() const;

  /// Gets the SeqAccessesZoneNode corresponding to the \p NodeZone under this
  /// SeqAccessesRegionNode
  SeqAccessesZoneNode *getZoneNode(Zone NodeZone);

  /// Gets the SeqAccess corresponding to the access \p I in \p NodeZone under
  /// this SeqAccessesRegionNode
  SeqAccess *getSeqAccess(const Zone *NodeZone, const Instruction *I);
};

/// @brief A node to record analysis zone
class SeqAccessesZoneNode {
  friend class BBsAnalyzer;
  friend class RegionAnalyzer;
  friend class LoopAnalyzer;

protected:
  using SeqAccessesMap = MapVector<ChainID, SetVector<SeqAccess *>>;

private:
  LLVMContext *Ctx;
  const DataLayout *DL;

  /// Represents the begin BB of this SeqAccessesZoneNode
  BasicBlock *RS;

  /// Represents the end BB of this SeqAccessesZoneNode
  BasicBlock *RE;

  /// Represents the RegionNode that this SeqAccessesZoneNode is under
  SeqAccessesRegionNode *Parent;

  /// Collects candidate stores
  InstListMap StoreRefs;

  /// Collects candidate loads
  InstListMap LoadRefs;

  /// Collects all SeqAccesses inferred in the zone
  SeqAccessesMap SeqAccesses;

  /// Adds a new inferred SeqAccess
  void addSeqAccess(Value *Obj, Type *T, ArrayRef<Instruction *> Chain,
                    SeqAccess::AccessDirection Dir, const SCEV *Start,
                    const SCEV *Len, Instruction *BP, Instruction *EP,
                    ArrayRef<std::pair<Value *, ConstantInt *>> Preds = None);

  /// Removes a SeqAccess
  void remove(SeqAccess *SA);

  /// Clears the SeqAccessesMap
  void clear();

public:
  SeqAccessesZoneNode(BasicBlock *RS, BasicBlock *RE,
                      SeqAccessesRegionNode *Parent)
      : Ctx(Parent->getContext()), DL(Parent->getDataLayout()), RS(RS), RE(RE),
        Parent(Parent) {}

  SeqAccessesZoneNode(const SeqAccessesZoneNode &) = delete;
  SeqAccessesZoneNode &operator=(const SeqAccessesZoneNode &) = delete;

  ~SeqAccessesZoneNode() { clear(); }

  /// Gets the begin BB of this SeqAccessesZoneNode
  BasicBlock *getZoneStart() const;

  /// Gets the end BB of this SeqAccessesZoneNode
  BasicBlock *getZoneEnd() const;

  /// Gets which RegionNode that this SeqAccessesZoneNode is under
  SeqAccessesRegionNode *getParent() const;

  /// Gets the SeqAccess corresponding to the access \p I in the zone
  SeqAccess *getSeqAccess(const Instruction *I);

  /// Gets the unique SeqAccess corresponding to the underlying object \p UObj
  /// in the zone. If there's not the unique one, return nullptr.
  SeqAccess *getUniqueSeqAccessOnUObj(const Value *UObj);
};

/// @brief Collects info for the loop that's going to be analyzed.
struct ToBeAnalyzedLoopInfo {
  Loop &L;
  BasicBlock *Preheader;
  BasicBlock *ExitBlock;
  const SCEV *BTC;
  PHINode *IndVar;

  ToBeAnalyzedLoopInfo(Loop &L) : L(L) {}
};

/// @brief Analysis that detects all sequential accesses.
class SeqAccessesInfo {
  friend class AnalyzerBase;
  friend class BBsAnalyzer;
  friend class RegionAnalyzer;
  friend class LoopAnalyzer;

protected:
  using SeqAccessesRegionNodeListMap =
      MapVector<const Region *, std::unique_ptr<SeqAccessesRegionNode>>;
  using BBRegionMap = MapVector<const BasicBlock *, const Region *>;
  using AccessZoneMap =
      MapVector<const Instruction *, std::pair<Zone, const Loop *>>;
  using LoopRegionMap = MapVector<const Loop *, const Region *>;
  using DiagFailureInfoMap = MapVector<const Instruction *, DiagFailureInfo *>;

private:
  /// Correlated Function
  Function *F;

  LLVMContext *Ctx;
  const DataLayout *DL;
  DominatorTree *DT;
  PostDominatorTree *PDT;
  LoopInfo *LI;
  OrderedInstructions *OI;
  RegionInfo *RI;
  AliasAnalysis *AA;
  ScalarEvolution *SE;
  ScalarEvolutionCanon *SEC;
  LoopPredicateAnalysis *LPA;
  OptimizationRemarkEmitter *ORE;

  /// True if source is OpenCL function
  bool IsOpenCL;

  /// Enable diagnostics or not
  bool EnableDiag;

  /// Records the topological order of the BBs
  DenseMap<const BasicBlock *, int> TopoOrderedBBs;

  /// Records the visited BBs
  SetVector<BasicBlock *> VisitedBBs;

  /// Records the visited Loops
  SetVector<Loop *> VisitedLoops;

  /// Records which region is corresponding to which SeqAccessesRegionNode
  SeqAccessesRegionNodeListMap SeqAccessesRegionMap;

  /// Collects up-to-dated sequential access zone inferred for an access
  AccessZoneMap AccessZone;

  /// Records which loop is corresponding to which region
  LoopRegionMap LoopRegion;

  /// Records diagnostics of failing to analyze/extend a sequential access
  DiagFailureInfoMap DiagFailureInfos;

  /// Records the loops that could not analyzed
  SetVector<Loop *> CouldNotAnalyzedLoops;

  /// Updates statistics of inferred sequential accesses
  void updateStatistics();

  /// Topological sort from \p BB
  int topologicalSort(BasicBlock *BB, int ID, SetVector<BasicBlock *> &Visited);

  /// Detects all sequential accesses in the function
  void calculate(Function &F);

  /// Processes regions in a function in the bottom-up fashion
  void process(Region &R);

  /// Detects all sequential accesses in the region
  void calculate(Region &R);

  /// Collects all accesses in topological in a region.
  void
  collectMayAccessesAndMayWrapsInRegion(std::vector<BasicBlock *> &WorkList,
                                        SeqAccessesRegionNode *RNode);

  /// Detects all sequential accesses in the zone.
  void calculate(SeqAccessesRegionNode *RNode, BasicBlock &BB);

  /// Collects all candidate BBs for inferring sequential accesses start from
  /// \p BB.
  void collectBBs(std::deque<BasicBlock *> &WorkList, BasicBlock &BB);

  /// Extends BB in region \p R.
  void extend(SeqAccessesRegionNode *RNode, Region &R);

  /// Merges BBs into each sets that can be a candidate zone for extending a
  /// sequential access chain
  void mergeSets(SetVector<const BasicBlock *> &MinSets, const BasicBlock *LMin,
                 const BasicBlock *RMin);
  SetVector<const BasicBlock *> getSetsOfDomPostDomRegions(BBRegionMap &WorkMap,
                                                           size_t s, size_t e);
  /// Collects candidate BBs in a region for extending or infer a sequential
  /// access
  void collectRegionBBs(BBRegionMap &WorkList,
                        std::deque<BasicBlock *> &RWorkList, BasicBlock &BB);

  /// Check if the loop \p L can be analyzed, if so record the loop info in
  /// \ret ToBeAnalyzedLoopInfo
  Optional<ToBeAnalyzedLoopInfo> getToBeAnalyzedLoopInfo(Loop &L,
                                                         ReflowDiagnostic &RD);

  /// Detects all sequential accesses in the loop.
  void calculate(SeqAccessesRegionNode *RNode, Loop &L);

  /// Adds new inferred sequential access zone into AccessZone
  void addAccessZone(const Instruction *AI, Zone NodeZone, Loop *L = nullptr);

  /// Updated the extended sequential access zone into AccessZone
  void updateAccessZone(const Instruction *AI, Zone NodeZone,
                        Loop *L = nullptr);

  /// Adds new diagnostics of failing to infer sequential access
  bool addDiagFailureInfo(const Instruction *AI,
                          DiagFailureInfo::FailureType FT,
                          bool ExtendAnalyzedSA = false,
                          Instruction *SI = nullptr, Loop *L = nullptr);

public:
  /// @name AccessZone iterators
  //@{
  using iterator = AccessZoneMap::iterator;
  using const_iterator = AccessZoneMap::const_iterator;

  iterator begin() { return AccessZone.begin(); }
  const_iterator begin() const { return AccessZone.begin(); }
  iterator end() { return AccessZone.end(); }
  const_iterator end() const { return AccessZone.end(); }
  //@}

  /// Checks if there isn't any inferred sequential accesses
  bool empty() const { return AccessZone.empty(); }

  /// Return number of inferred sequential accesses
  unsigned size() const { return AccessZone.size(); }

  /// Gets the access from the AccessZone iterator \p I
  const Instruction *getAccess(iterator I) { return I->first; }
  const Instruction *getAccess(const_iterator I) { return I->first; }
  /// Gets the corresponding loop from the AccessZone iterator \p I
  const Loop *getAccessInferredLoop(iterator I) { return I->second.second; }
  const Loop *getAccessInferredLoop(const_iterator I) {
    return I->second.second;
  }

  /// @name DiagFailureInfos iterators
  //@{
  using diterator = DiagFailureInfoMap::iterator;
  using const_diterator = DiagFailureInfoMap::const_iterator;

  diterator diag_begin() { return DiagFailureInfos.begin(); }
  const_diterator diag_begin() const { return DiagFailureInfos.begin(); }
  diterator diag_end() { return DiagFailureInfos.end(); }
  const_diterator diag_end() const { return DiagFailureInfos.end(); }
  //@}

  /// Checks if there isn't any diagnostics
  bool diag_empty() const { return DiagFailureInfos.empty(); }

  /// Gets the access from the DiagFailureInfos iterator \p I
  const Instruction *getAccess(diterator I) { return I->first; }
  const Instruction *getAccess(const_diterator I) { return I->first; }

  /// Gets the diagnostics from the DiagFailureInfos iterator \p I
  DiagFailureInfo *getDiagFailureInfo(diterator I) { return I->second; }
  DiagFailureInfo *getDiagFailureInfo(const_diterator I) { return I->second; }

  ArrayRef<Loop *> getCouldNotAnalyzedLoops() {
    return CouldNotAnalyzedLoops.getArrayRef();
  }

  explicit SeqAccessesInfo() = default;

  ~SeqAccessesInfo() { releaseMemory(); }

  SeqAccessesInfo(const SeqAccessesInfo &) = delete;
  SeqAccessesInfo &operator=(const SeqAccessesInfo &) = delete;

  void print(raw_ostream &OS) const;
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  void dump() const;
#endif

  /// Calculate the sequential access
  void recalculate(Function &F_, DominatorTree *DT_, PostDominatorTree *PDT_,
                   LoopInfo *LI_, OrderedInstructions *OI_, RegionInfo *RI_,
                   AliasAnalysis *AA_, ScalarEvolution *SE_,
                   ScalarEvolutionCanon *SEC_, LoopPredicateAnalysis *LPA_,
                   OptimizationRemarkEmitter *ORE_, bool EnableDiag_ = false);

  /// Gets the corresponding SeqAccessesRegionNode from \p R
  SeqAccessesRegionNode *getSeqAccessesRegionNode(const Region *R);

  /// Gets the corresponding Region from \p L
  const Region *getLoopRegion(const Loop *L);

  /// Checks if there's sequential access inferred on \p I
  bool isContainedInSeqAccess(const Instruction *I);

  /// Gets the sequential access zone if there's a sequential access inferred on
  /// \p I
  Zone *getSeqAccessZone(const Instruction *I);

  /// Gets the SeqAccessesZoneNode if there's a sequential access inferred on \p
  /// I
  SeqAccessesZoneNode *getSeqAccessZoneNode(const Instruction *I);

  /// Gets the corresponding loop if there's a a sequential access inferred on
  /// \p I on the loop
  const Loop *getAccessInferredLoop(const Instruction *I);

  /// Gets the sequential access length if there's a sequential access inferred
  /// on \p I
  const SCEV *getSeqAccessLen(const Instruction *I);

  /// Return true if analysis info is for OpenCL function
  bool isForOpenCL();

  void releaseMemory();

  void verifyAnalysis() const;
};

/// @brief base class of an access analyzer.
class AnalyzerBase {
protected:
  SeqAccessesInfo *SAI;
  SeqAccessesZoneNode *SN;
  LLVMContext *Ctx;
  const DataLayout *DL;
  LoopInfo *LI;
  DominatorTree *DT;
  AliasAnalysis *AA;
  ScalarEvolution *SE;
  ScalarEvolutionCanon *SEC;
  ReflowDiagnostic &RD;

  /// Enable diagnostics or not
  bool EnableDiag;

  /// Checks if there's an inferred sequential access on \p I
  bool isCandidateAccessInRegions(Instruction *I);

  /// Checks if the access is on an interface that support sequential accesses
  bool supportSequentialAccessInterface(Value *Ptr, LoopInfo *LI = nullptr);

  /// Gets ChainID for candidate access.
  ChainID getCandidateAccessID(Value *AccessInst, LoopInfo *LI = nullptr,
                               bool EnableUnalignBurst = true);

  /// Checks if the accesses are consecutive
  bool areConsecutiveAccesses(Value *A, Value *B,
                              const SCEV *ALen = nullptr) const;
  bool areConsecutivePointers(Value *PtrA, Value *PtrB, APInt PtrDelta,
                              unsigned Depth = 0,
                              const SCEV *ALen = nullptr) const;
  bool isLegalToComputeConsecutiveness(Value *PtrA, Value *PtrB) const;
  bool lookThroughComplexAddresses(Value *PtrA, Value *PtrB, APInt PtrDelta,
                                   unsigned Depth = 0) const;
  bool lookThroughSelects(Value *PtrA, Value *PtrB, APInt PtrDelta,
                          unsigned Depth = 0) const;

  /// Gets underlying MemoryLocation for \p StartI with \p ChainSize size
  MemoryLocation getChainMemoryLocation(Instruction *StartI, Type *VT,
                                        size_t ChainSize);

  /// Gets access data type
  Type *getAccessElementType(ArrayRef<Instruction *> Chain);
  Type *getAccessElementType(Instruction *CI);

  /// Checks if \p I has no side effect
  virtual bool hasNoSideEffect(Instruction *I);

  /// Checks if sequential access chain starts with \p AI is in a valid
  /// sequential access inference region
  virtual bool isValidSeqAccessRegion(Instruction *AI = nullptr);

public:
  AnalyzerBase(SeqAccessesInfo *SAI, SeqAccessesZoneNode *SN, LLVMContext *Ctx,
               const DataLayout *DL, LoopInfo *LI, DominatorTree *DT,
               AliasAnalysis *AA, ScalarEvolution *SE,
               ScalarEvolutionCanon *SEC, ReflowDiagnostic &RD,
               bool EnableDiag = false)
      : SAI(SAI), SN(SN), Ctx(Ctx), DL(DL), LI(LI), DT(DT), AA(AA), SE(SE),
        SEC(SEC), RD(RD), EnableDiag(EnableDiag) {}
  virtual ~AnalyzerBase() = default;
};

/// @brief An abstract class of an access analyzer.
class Analyzer : public AnalyzerBase {
  using AnalyzerBase::AnalyzerBase;

protected:
  /// Collects candidate accesses
  virtual void collectAccesses(std::deque<BasicBlock *> &WorkList) = 0;

  /// Infers sequential accesses from load/store chain
  virtual void inferRefs(InstListMap &AccessRefs) = 0;
  virtual void inferChain(ArrayRef<Instruction *> Accesses) = 0;
  virtual unsigned getSeqAccessPrefixEndIdx(ArrayRef<Instruction *> Chain,
                                            Instruction *FromI = nullptr,
                                            Instruction *ToI = nullptr) = 0;
  virtual void
  inferChain(ArrayRef<Instruction *> Chain,
             SmallPtrSet<Instruction *, 16> *InstructionsProcessed) = 0;
  virtual void inferChain(ArrayRef<Instruction *> Chain, Value *StartV, Type *T,
                          Instruction *BP, Instruction *EP) = 0;

public:
  /// Infers sequential accesses
  virtual void infer(std::deque<BasicBlock *> &WorkList) = 0;

  virtual ~Analyzer() = default;
};

/// @brief An access analyzer for a BB zone.
class BBsAnalyzer : public Analyzer {
  using Analyzer::Analyzer;

  /// @name Base analyze functions
  //@{
  void collectAccesses(std::deque<BasicBlock *> &WorkList);
  void inferRefs(InstListMap &AccessRefs);
  void inferChain(ArrayRef<Instruction *> Accesses);
  unsigned getSeqAccessPrefixEndIdx(ArrayRef<Instruction *> Chain,
                                    Instruction *FromI = nullptr,
                                    Instruction *ToI = nullptr);
  void inferChain(ArrayRef<Instruction *> Chain,
                  SmallPtrSet<Instruction *, 16> *InstructionsProcessed);
  void inferChain(ArrayRef<Instruction *> Chain, Value *StartV, Type *T,
                  Instruction *BP, Instruction *EP);
  //@}

  /// Searches on all of the given accesses and find all of the pairs of
  /// accesses that follow each other.
  void exploreConsecutiveChain(ArrayRef<Instruction *> Accesses,
                               std::vector<int> &ConsecutiveChain,
                               SetVector<int> &Heads, SetVector<int> &Tails);
  std::pair<BasicBlock::iterator, BasicBlock::iterator>
  getBoundaryInstrs(ArrayRef<Instruction *> Chain);

public:
  void infer(std::deque<BasicBlock *> &WorkList);
};

/// @brief An access analyzer for a Region zone.
class RegionAnalyzer : public Analyzer {
  OrderedInstructions *OI;

  /// @name Base analyze functions
  //@{
  void collectAccesses(std::deque<BasicBlock *> &WorkList);
  void inferRefs(InstListMap &AccessRefs);
  void inferChain(ArrayRef<Instruction *> Accesses);
  unsigned getSeqAccessPrefixEndIdx(ArrayRef<Instruction *> Chain,
                                    Instruction *FromI = nullptr,
                                    Instruction *ToI = nullptr);
  void inferChain(ArrayRef<Instruction *> Chain,
                  SmallPtrSet<Instruction *, 16> *InstructionsProcessed);
  void inferChain(ArrayRef<Instruction *> Chain, Value *StartV, Type *T,
                  Instruction *BP = nullptr, Instruction *EP = nullptr);
  //@}

  /// Searches on all of the given accesses and find all of the pairs of
  /// accesses that follow each other.
  void exploreConsecutiveChain(ArrayRef<Instruction *> Accesses,
                               std::vector<int> &ConsecutiveChain);

  /// Check if there are side effect instructions in between the candidate \p
  /// Chain
  bool hasSideEffectInstruction(ArrayRef<Instruction *> Chain,
                                MemoryLocation &CLoc,
                                SmallVectorImpl<Instruction *> &MayAccessRefs,
                                SetVector<Instruction *> &MemoryInstrs,
                                SetVector<Instruction *> &ChainInstrs);
  bool hasSideEffectInstruction(ArrayRef<Instruction *> Chain,
                                MemoryLocation &CLoc,
                                SetVector<Instruction *> &MemoryInstrs,
                                SetVector<Instruction *> &ChainInstrs,
                                Region *R);

public:
  RegionAnalyzer(SeqAccessesInfo *SAI, SeqAccessesZoneNode *SN,
                 LLVMContext *Ctx, const DataLayout *DL, LoopInfo *LI,
                 DominatorTree *DT, AliasAnalysis *AA, ScalarEvolution *SE,
                 ScalarEvolutionCanon *SEC, ReflowDiagnostic &RD,
                 OrderedInstructions *OI, bool EnableDiag = false)
      : Analyzer(SAI, SN, Ctx, DL, LI, DT, AA, SE, SEC, RD, EnableDiag),
        OI(OI) {}

  void infer(std::deque<BasicBlock *> &WorkList);
};

/// @brief An access analyzer for a Loop zone.
class LoopAnalyzer : public AnalyzerBase {
  ToBeAnalyzedLoopInfo &ALI;
  LoopPredicateAnalysis *LPA;

  /// Returns true if \p BB will be executed in all iterations
  bool isExecutedInAllIterations(BasicBlock *BB);

  /// Add explicit sequential access info from sequential access intrinsics
  void addExplicitSAInfo();

  /// Collects candidate accesses
  void collectAccesses();

  /// Gets SCEVAddRec for \p V
  const SCEVAddRecExpr *getAsAddRec(PredicatedScalarEvolution &PSE, Value *V,
                                    SeqAccess *SA = nullptr);

  /// Gets the distance between K iteration SCEV and (K+M) iteration SCEV
  /// from \p V, where M = lcm(IndvarStride, Divs)/IndvarStride and
  /// \p ModTerm = indvar % Divs == Rem
  const SCEV *getDistBetweenSteps(PredicatedScalarEvolution &PSE,
                                  Instruction *I, Value *ModTerm);

  /// Gets the distance after one step and now.
  const SCEV *getDistBetweenOneStep(PredicatedScalarEvolution &PSE,
                                    Instruction *I, SeqAccess *SA);

  /// Checks if the candidate access has legal stride for analyzing
  const SCEV *getValidAccessPattern(PredicatedScalarEvolution &PSE,
                                    Instruction *I, SeqAccess *SA,
                                    Value *ModTerm, bool IsSingleBTC);
  bool hasLegalStride(PredicatedScalarEvolution &PSE, Instruction *I,
                      SeqAccess *SA, Value *ModTerm, bool IsSingleBTC);
  bool hasLegalStride(const SCEV *ValidPattern, const SCEV *ScStride,
                      Instruction *I, SeqAccess *SA);
  bool seqAccessHasLegalStride(SeqAccess *SA, const SCEV *ScStride);
  bool singleAccessHasLegalStride(Instruction *I, const SCEV *ScStride,
                                  const SCEV *ValidPattern);

  /// Gets stride in element-word unit.
  unsigned getStrideInNumElts(PredicatedScalarEvolution &PSE, Instruction *I,
                              SeqAccess *SA, Value *ModTerm);

  /// Gets the start address of the inferred sequential accesses chain
  const SCEV *getStartAddr(PredicatedScalarEvolution &PSE, SeqAccess *SA,
                           Value *Ptr, IntervalInfo *Interval,
                           bool IsExeAllItrsOrOnlyGuardByInvariantPreds,
                           Value *ModTerm);

  /// Gets the burst size(in words) of the inferred sequential accesses chain
  const SCEV *getBurstSize(BasicBlock *BB, IntervalInfo *Interval,
                           bool IsExeAllItrsOrOnlyGuardByInvariantPreds,
                           Type *SizeTy, SeqAccess *SA, Value *ModTerm);

  /// Adds `AccessInCondBranch` kind diagnostic failure for access \p AI of loop
  /// \p L
  void addDiagFailureAccessInCondBranch(Instruction *AI, Loop *L);

  /// Gets the BB that the begin of the sequential access chain that starts with
  /// \p AI resides.
  BasicBlock *getAccessBeginBB(Instruction *AI);

  /// Infers sequential accesses from load/store
  void inferRefs(InstListMap &AccessRefs);
  void inferChain(Instruction *AI, SeqAccess *SA = nullptr);
  void
  inferChain(PredicatedScalarEvolution &PSE, Instruction *AI, Type *T,
             SeqAccess *SA, IntervalInfo *Interval, Value *ModTerm,
             ArrayRef<std::pair<Value *, ConstantInt *>> LoopInvariantPreds);

  /// Check if there are side effect instructions in between the loop iterations
  /// and if the access pointer itself is wrapping.
  bool hasSideEffectInLoop(PredicatedScalarEvolution &PSE, Instruction *AI,
                           MemoryLocation &CLoc, Instruction *SI, Loop &L);
  bool hasSideEffectInstructionOrIsWrappingAccess(
      PredicatedScalarEvolution &PSE, Region *R, Instruction *AI,
      MemoryLocation &CLoc, SeqAccess *SA);
  bool hasSideEffectInstruction(PredicatedScalarEvolution &PSE, Instruction *AI,
                                MemoryLocation &CLoc,
                                SmallVectorImpl<Instruction *> &MayAccessRefs,
                                SeqAccess *SA);
  bool isWrappingAccess(Instruction *AI,
                        SmallVectorImpl<Instruction *> &MayWraps);
  bool areAccessDataSetOverlap(PredicatedScalarEvolution &PSE, Instruction *LHS,
                               Instruction *RHS);

  /// Checks if \p I has no side effect
  bool hasNoSideEffect(Instruction *I) override;

  /// Checks if sequential access chain starts with \p AI is in a valid
  /// sequential access inference region
  bool isValidSeqAccessRegion(Instruction *AI = nullptr) override;

public:
  LoopAnalyzer(SeqAccessesInfo *SAI, SeqAccessesZoneNode *SN, LLVMContext *Ctx,
               const DataLayout *DL, DominatorTree *DT, AliasAnalysis *AA,
               ScalarEvolution *SE, ScalarEvolutionCanon *SEC,
               ReflowDiagnostic &RD, LoopInfo *LI, ToBeAnalyzedLoopInfo &ALI,
               LoopPredicateAnalysis *LPA, bool EnableDiag = false)
      : AnalyzerBase(SAI, SN, Ctx, DL, LI, DT, AA, SE, SEC, RD, EnableDiag),
        ALI(ALI), LPA(LPA) {}

  void infer();
};

/// The SeqAccessesInfo pass detects all sequential accesses in a function.
class SeqAccessesInfoPass : public FunctionPass {
  /// Detects and collects all sequential accesses
  SeqAccessesInfo SI;

public:
  static char ID;

  SeqAccessesInfoPass() : FunctionPass(ID) {
    initializeSeqAccessesInfoPassPass(*PassRegistry::getPassRegistry());
  }

  ~SeqAccessesInfoPass() = default;

  SeqAccessesInfo &getSeqAccessesInfo() { return SI; }

  const SeqAccessesInfo &getSeqAccessesInfo() const { return SI; }

  /// @name FunctionPass interface
  //@{
  bool runOnFunction(Function &F) override;
  void releaseMemory() override;
  void verifyAnalysis() const override;
  void getAnalysisUsage(AnalysisUsage &AU) const override;
  void print(raw_ostream &OS, const Module *) const override;
  void dump() const;
  //@}

  bool skipFunction(const Function &F) const;
};

/// IR annotation writer for emitting analyzed sequential access information for
/// regions.
class SeqAccessesInfoWriter : public AssemblyAnnotationWriter {
  friend class SeqAccessesInfo;

  /// Correlated SeqAccessesInfo
  const SeqAccessesInfo *SI;

  ScalarEvolution &SE;

  /// Print Loop \p L information
  void printLoopInfo(const Loop *L, formatted_raw_ostream &OS) const;

  /// Print region information of SeqAccess \p SA
  void printSeqAccessRegionInfo(const SeqAccess *SA,
                                formatted_raw_ostream &OS) const;

public:
  SeqAccessesInfoWriter(const SeqAccessesInfo *SI, ScalarEvolution &SE)
      : SI(SI), SE(SE) {}

  void emitInstructionAnnot(const Instruction *I,
                            formatted_raw_ostream &OS) override {
    auto CSI = const_cast<SeqAccessesInfo *>(SI);
    auto ZN = CSI->getSeqAccessZoneNode(I);
    if (!ZN)
      return;

    auto SA = ZN->getSeqAccess(I);
    if (!SA)
      return;
    auto FAI = SA->getSeqAccessChainBegin();
    if (FAI != I)
      return;

    printSeqAccessRegionInfo(SA, OS);

    SA->print(OS);
  }
};

} // namespace llvm

#endif
